#include "predictor.h"
#include "types.h"
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <string>

using namespace std;

// ---------------------------------------------------------------------------------------------------------------------
// TYPES.h
// ---------------------------------------------------------------------------------------------------------------------
// Project:	Alpha Branch Predictor
// Authors:	Jabeer Ahmed, 
// 			Omar Mohsin, 
// 			Fadi Butti
// Course:	ECE - 586 (Winter 2013)
// Prof:	Mark Faust
// Portland State University
// ---------------------------------------------------------------------------------------------------------------------

#ifndef __TYPES_H__
#define __TYPES_H__

typedef unsigned int uint;

#endif 	__TYPES_H__

// ---------------------------------------------------------------------------------------------------------------------
// COUNTERS.h
// ---------------------------------------------------------------------------------------------------------------------
// Project:	Alpha Branch Predictor
// Authors:	Jabeer Ahmed, 
// 			Omar Mohsin, 
// 			Fadi Butti
// Course:	ECE - 586 (Winter 2013)
// Prof:	Mark Faust
// Portland State University
// ---------------------------------------------------------------------------------------------------------------------

#ifndef __COUNTERS_H__
#define __COUNTERS_H__

struct counter2
{
	uint ui:2;
	counter2()			:ui(1)	{};
	counter2(int val)	:ui(val){};
	counter2(char val)	:ui(val){};
	counter2(short val)	:ui(val){};
	counter2(uint val)	:ui(val){};

	counter2& operator++(int){this->ui++; return *this;}
	counter2& operator--(int){this->ui--; return *this;}
	bool   isTaken()	{ return ui & 0x2;}
	string isTakenStr()	{ return (isTaken()) ? string("taken"):string("not taken");}
    friend ostream& operator<<(ostream& lhs, const counter2& rhs)
    {
        return lhs << rhs.ui; 
    }
};

struct counter3
{
	uint ui:3;
	counter3()			:ui(3)	{};
	counter3(int val)	:ui(val){};
	counter3(char val)	:ui(val){};
	counter3(short val)	:ui(val){};
	counter3(uint val)	:ui(val){};
	bool   isTaken()	{ return ui & 0x4;}
	string isTakenStr()	{ return (isTaken()) ? string("taken"):string("not taken");}
	counter3& operator++(int){this->ui++; return *this;}
	counter3& operator--(int){this->ui--; return *this;}
    friend ostream& operator<<(ostream& lhs, const counter3& rhs)
    {
        return lhs << rhs.ui; 
    }
};

#endif 	// __COUNTERS_H__

// ---------------------------------------------------------------------------------------------------------------------
// SHIFT_REGISTERS.h
// ---------------------------------------------------------------------------------------------------------------------
// Project:	Alpha Branch Predictor
// Authors:	Jabeer Ahmed, 
// 			Omar Mohsin, 
// 			Fadi Butti
// Course:	ECE - 586 (Winter 2013)
// Prof:	Mark Faust
// Portland State University
// ---------------------------------------------------------------------------------------------------------------------

#ifndef __SHIFT_REGISTERS_H__
#define __SHIFT_REGISTERS_H__

struct shift_reg10
{
	uint bits:10;
	shift_reg10():bits(0){};
	shift_reg10& operator++(int){bits = bits<<1 | 0x1; return *this;}	// insert 1
	shift_reg10& operator--(int){bits<<=1; return *this;} 				// insert 0 
};

struct shift_reg12
{
	uint bits:12;
	shift_reg12():bits(0){};
	shift_reg12& operator++(int){bits = bits<<1 | 0x1; return *this;}	// insert 1
	shift_reg12& operator--(int){bits<<=1; return *this;} 				// insert 0 
};

struct shift_reg 						
{
	bool *bits; 									// bool array for storing bits
	uint size; 										// size of the register
	uint val; 										// decimal value of the register
	shift_reg(int len){  							// contructor with length as input
		bits = (bool*)calloc(len,1); 				// Make the bool array of size len
		size = len; 								// set size of register to len
		val  = 0;									// initialize value of reg to 0
	}
	~shift_reg(){ 									// destructor called when reg is freed
		if(bits){
			free(bits);								// free the bits array
            bits = 0;
        }
    }
    shift_reg(const shift_reg& reg){
        this->size = reg.size;
        this->val = reg.val;
        this->bits = (bool*)calloc(this->size,1);
        memcpy(this->bits, reg.bits, this->size);
    }

    shift_reg& operator= (const shift_reg& reg){
        if (this != &reg){
            this->size = reg.size;
            this->val = reg.val;
            this->bits = (bool*)calloc(this->size,1);
            memcpy(this->bits, reg.bits, this->size);
        }
        return *this;
    }
    
	void push(bool bit){ 							// pushes bits in and calcs the value of the register
		val = 0; 									// initialize val
		for (int i=size-1; i>0;i--)					// loop through
		{
			bits[i] = bits[i-1];					// shift the bits down the array
			val<<=1; 								// shift val
			val|=bits[i]; 							// and push the bit in
		}
		bits[0] = bit;								// push the new bit in the head of the array
		val<<=1;									// shift val
		val|=bit; 									// push the bit
	}

    friend ostream& operator<<(ostream& lhs, const shift_reg& rhs) 	// prints out the bits
    {																// e.g. usage: cout << reg << endl;
    	lhs << " b";
        uint val = 0;
        for (int i=rhs.size-1; i>=0;i--){
			lhs << rhs.bits[i]; 
			val<<=1;
			val|=rhs.bits[i];
		}
		return lhs << " val = " << rhs.val;
    }
};

#endif 	// __SHIFT_REGISTERS_H__

// ---------------------------------------------------------------------------------------------------------------------
// GLOBAL_PREDICTION_TABLE.h
// ---------------------------------------------------------------------------------------------------------------------
// Project:	Alpha Branch Predictor
// Authors:	Jabeer Ahmed, 
// 			Omar Mohsin, 
// 			Fadi Butti
// Course:	ECE - 586 (Winter 2013)
// Prof:	Mark Faust
// Portland State University
// ---------------------------------------------------------------------------------------------------------------------

#ifndef __GLOBAL_PREDICTION_TABLE_H__
#define __GLOBAL_PREDICTION_TABLE_H__

#define GLOBAL_TABLE_SIZE 4096
#define GLOBAL_TABLE_INDX(indx) indx & (GLOBAL_TABLE_SIZE - 1)

class global_prediction_table {
	counter2 *table;
public:
	global_prediction_table(){
		table = new  counter2[GLOBAL_TABLE_SIZE];
	}
	~global_prediction_table(){
		delete table;
	}
	counter2& operator[] (uint indx){
		return table[GLOBAL_TABLE_INDX(indx)];
	} 
};

class choice_prediction {
	counter2 *table;
public:
	choice_prediction(){
		table = new  counter2[GLOBAL_TABLE_SIZE];
	}
	~choice_prediction(){
		delete table;
	}
	counter2& operator[] (uint indx){
		return table[GLOBAL_TABLE_INDX(indx)];
	} 
};


#endif 	// __GLOBAL_PREDICTION_TABLE_H__

// ---------------------------------------------------------------------------------------------------------------------
// LOCAL_HISTORY_TABLE.h
// ---------------------------------------------------------------------------------------------------------------------
// Project:	Alpha Branch Predictor
// Authors:	Jabeer Ahmed, 
// 			Omar Mohsin, 
// 			Fadi Butti
// Course:	ECE - 586 (Winter 2013)
// Prof:	Mark Faust
// Portland State University
// ---------------------------------------------------------------------------------------------------------------------

#ifndef __LOCAL_HISTORY_TABLE_H__
#define __LOCAL_HISTORY_TABLE_H__

#define LOCAL_TABLE_SIZE 1024
#define LOCAL_TABLE_INDX(pc_address) pc_address & (LOCAL_TABLE_SIZE - 1)

class local_history_table {
	shift_reg10 *table;
public:
	local_history_table(){
		table = new  shift_reg10[LOCAL_TABLE_SIZE];
	}
	local_history_table(int size){
		table = new  shift_reg10[size];
	}
	~local_history_table(){
		delete table;
	}
	shift_reg10& operator[] (int pc_addr){
		return table[LOCAL_TABLE_INDX(pc_addr)];
	} 
};

class local_prediction_table {
	counter3 *table;
public:
	local_prediction_table(){
		table = new  counter3[LOCAL_TABLE_SIZE];
	}
	local_prediction_table(int size){
		table = new  counter3[size];
	}
	~local_prediction_table(){
		delete table;
	}
	counter3& operator[] (int pc_addr){
		return table[LOCAL_TABLE_INDX(pc_addr)];
	} 
};

#endif 	// __LOCAL_HISTORY_TABLE_H__

// ---------------------------------------------------------------------------------------------------------------------
// DEBUGGER.h
// ---------------------------------------------------------------------------------------------------------------------
// Project:	Alpha Branch Predictor
// Authors:	Jabeer Ahmed, 
// 			Omar Mohsin, 
// 			Fadi Butti
// Course:	ECE - 586 (Winter 2013)
// Prof:	Mark Faust
// Portland State University
// ---------------------------------------------------------------------------------------------------------------------
/* 
---------------------------------------------------------------------------------------------------------------------
Redefinition of branch_record_c & op_state_c
---------------------------------------------------------------------------------------------------------------------
These classes will defined only if the debugger is compiled without the framework 
for debugging purpose. This will allow for the debugger to read the ASCII text file 
without the need to compile the framework.
***** ASSUMING THAT tread.h & op_state.h WILL BE COMPILED BEFORE THIS FILE *****
*/
#ifndef TREAD_H_SEEN
struct branch_record_c
{
    uint   instruction_addr;       // the branch's PC (program counter)                      
    uint   instruction_next_addr;  // the PC of the static instruction following the branch  
    bool   is_indirect;            // true if the target is computed; false if it's PC-rel; returns are also considered indirect
    bool   is_conditional;         // true if the branch is conditional; false otherwise     
    bool   is_call;                // true if the branch is a call; false otherwise          
    bool   is_return;              // true if the branch is a return; false otherwise        
    bool   is_taken;
    branch_record_c(){
        instruction_addr        = 0;     
        instruction_next_addr   = 0; 
        is_indirect             = false;          
        is_conditional          = false;       
        is_call                 = false;             
        is_return               = false;
        is_taken                = false;
    }
};

struct op_state_c
{
	/* data */
};
#endif 

/* 
---------------------------------------------------------------------------------------------------------------------
Debugger & Statistics   
---------------------------------------------------------------------------------------------------------------------
*/
#ifndef __DEBUGGER_H__
#define __DEBUGGER_H__

#ifdef TREAD_H_SEEN					// if the debugger is used with the framework
#include "tread.h"					// we need to include tread.h
#endif						

#define TF(tf) (tf) ? "True" : "False"

struct br_stat
{
	uint num_indirect_br;
	uint num_pc_rel_br;
	uint num_conditional_br;
	uint num_unconditional_br;
	uint num_calls;
	uint num_returns;
	int  call_stack;
	uint total_call_stack;
	float avg_call_stack;
	uint max_call_stack;	

	br_stat(): 
		num_indirect_br(0),
		num_pc_rel_br(0),
		num_conditional_br(0),
		num_unconditional_br(0),
		num_calls(0),
		num_returns(0),
		call_stack(0),
		total_call_stack(0),
		avg_call_stack(0),
		max_call_stack(0){}	
};

void write_statistics(const char* file, const br_stat* stat)
{
	ofstream stat_file ("stat.txt");
	if (stat_file.is_open()){
		stat_file << "Branch Statistics" << endl;
		stat_file << "num_indirect_br:\t\t" << stat->num_indirect_br << endl;
		stat_file << "num_pc_rel_br:\t\t\t" << stat->num_pc_rel_br << endl;
		stat_file << "num_conditional_br:\t\t" << stat->num_conditional_br << endl;
		stat_file << "num_unconditional_br:\t" << stat->num_unconditional_br << endl;
		stat_file << "num_calls:\t\t\t\t" << stat->num_calls << endl;
		stat_file << "num_returns:\t\t\t" << stat->num_returns << endl;
		stat_file << "call_stack:\t\t\t\t" << stat->call_stack << endl;
		stat_file << "total_call_stack:\t\t" << stat->total_call_stack << endl;
		stat_file << "avg_call_stack:\t\t\t" << stat->avg_call_stack << endl;
		stat_file << "max_call_stack:\t\t\t" << stat->max_call_stack << endl;	
		stat_file.close();
	}
}

bool initialize_debugger(const char* file)
{
	FILE *fp = fopen(file, "w");
	bool res = false;
	if (fp){
		fprintf(fp, "Branch_PC\t\tactual_target\tis_cond\t\tis_call\t\tis_return\tis_taken\tis_indir\n");
		res = true;
	}
	fclose(fp);	
	return res;
}

void write_prediction(const char* file, const branch_record_c* br, bool taken, uint actual_target_address)
{
	FILE *fp = fopen(file,"a");
	if (fp){
		fprintf(fp, "%p\t\t%p\t\t%s\t\t%s\t\t%s\t\t%s\t\t%s\n", br->instruction_addr, (int)actual_target_address, TF(br->is_indirect), TF(br->is_conditional),TF(br->is_call),TF(br->is_return),TF(taken));
	}
	fclose(fp);
}

#ifndef TREAD_H_SEEN
void initialize_reader(ifstream& file)
{
	string line;
	if (file.is_open() && file.good()){
		getline(file,line);
	}
}

void read_prediction(ifstream& file, branch_record_c* br)
{
    uint target, pc;
    char tf[5][8];
    string line;
	if (file.is_open() && file.good()){
		getline(file,line);
        sscanf(line.c_str(), "%x\t\t%x\t\t%s\t\t%s\t\t%s\t\t%s\t\t%s\n",&pc,&target,tf[0],tf[1],tf[2],tf[3],tf[4]);
        br->instruction_addr = pc;
        br->instruction_next_addr = target;
        br->is_indirect     = strcmp("True", tf[0]);
        br->is_conditional  = strcmp("True", tf[1]);
        br->is_call         = strcmp("True", tf[2]);        
        br->is_return       = strcmp("True", tf[3]);
        br->is_taken        = strcmp("True", tf[4]);
    }
}
#endif 	// TREAD_H_SEEN

#endif 	// __DEBUGGER_H__

// ---------------------------------------------------------------------------------------------------------------------
// PREDICTOR.cc
// ---------------------------------------------------------------------------------------------------------------------
// Project:	Alpha Branch Predictor
// Authors:	Jabeer Ahmed, 
// 			Omar Mohsin, 
// 			Fadi Butti
// Course:	ECE - 586 (Winter 2013)
// Prof:	Mark Faust
// Portland State University
// ---------------------------------------------------------------------------------------------------------------------

#define NOT_TAKEN 	0
#define TAKEN 		1

/*
---------------------------------------------------------------------------------------------------------------------
OBJECTS & VARIABLES 
---------------------------------------------------------------------------------------------------------------------
*/

local_history_table 	local_history; 							// Local History Table (10-bit shift registers) 
local_prediction_table	local_predictor;						// Local Predictor Table (3-bit saturation counters)
shift_reg 			  	path_history(12);						// Path History (12-bit shift register)
global_prediction_table global_predictor;						// Global Predictor Table (2-bit saturation counters) 
choice_prediction 		predicton_chooser;						// Choice Prediction (2-bit saturation counters)
bool 					is_debugger_initialized = false;		// flag to initailize debugger 							//<--- Debug	
br_stat 				stat;																							//<--- Debug	
uint 					print_counter = 0;

/*
---------------------------------------------------------------------------------------------------------------------	
Statistics
---------------------------------------------------------------------------------------------------------------------	
*/																															

void update_statistics(const char* file, const branch_record_c* br)														//<--- Debug
{

	if (br->is_indirect)										// if the branch is indirect
		stat.num_indirect_br++;									// increment indirect counter
	else														// else
		stat.num_pc_rel_br++;									// increment pc_relative counter	

	if (br->is_conditional)										// if the branch is conditional
		stat.num_conditional_br++;								// increment conditional counter
	else														// else
		stat.num_unconditional_br++;							// increment unconditional counter	

	if (br->is_call){											// if its a procedure call
		stat.num_calls++;										// increment call counter
		stat.call_stack++;										// increment the call_stack depth
		stat.total_call_stack+=stat.call_stack;					// increase the total_call_stack depth
		stat.avg_call_stack = (float)stat.total_call_stack/stat.num_calls; // calculate the current average stack depth
		if (stat.call_stack > stat.max_call_stack)				// check for max call stack
			stat.max_call_stack = stat.call_stack;				
	}

	if (br->is_return){											// if its a procedure return
		stat.num_returns++;										// increment the return counter
		stat.call_stack--;										// decrement the call_stack
		if (stat.call_stack < 0)
		{
			printf("CALL STACK WENT NEGATIVE\n");
			stat.call_stack = 0;
		}
	}
	if ((++print_counter)%100 == 0)								// update the file every hundred times
		write_statistics(file, &stat);
}

/* 
---------------------------------------------------------------------------------------------------------------------
BRANCH TARGET PREDICTION 
---------------------------------------------------------------------------------------------------------------------
*/


/* 
---------------------------------------------------------------------------------------------------------------------
ALPHA BRANCH PREDICTOR - Refer to fig: 4 of "The Alpha 21264 microprocessor" paper for an illustrative description 
---------------------------------------------------------------------------------------------------------------------
*/

bool globalBranchPrediction(const branch_record_c* br)
{
	return NOT_TAKEN;
}

bool localBranchPrediction(const branch_record_c* br)
{
	uint pc = br->instruction_addr;								// Get the current PC
	shift_reg10 pattern = local_history[pc];					// Use the PC to index into the local history table to -  
																// access the local branch history pattern
	counter3 local_prediction = local_predictor[pattern.bits];	// Use the 10 bit pattern to index into the local branch
	return local_prediction.isTaken();							// predictor table and return if it is taken or not
}

bool alphaBranchPrediction(const branch_record_c* br)
{
	bool local_prediction 	= localBranchPrediction(br); 		// Get the local branch prediction
	bool global_prediction	= globalBranchPrediction(br);    	// Get the global branch prediction 

	return NOT_TAKEN;											
}	

/* 
---------------------------------------------------------------------------------------------------------------------
SIMULATOR INTERFACE 
---------------------------------------------------------------------------------------------------------------------
*/

bool PREDICTOR::get_prediction(const branch_record_c* br, const op_state_c* os, uint *predicted_target_address)
{
    bool prediction = alphaBranchPrediction(br);				// Perform alpha branch prediction
    return prediction;   										
}

// Update the predictor after a prediction has been made.  This should accept
// the branch record (br) and architectural state (os), as well as a third
// argument (taken) indicating whether or not the branch was taken.
void PREDICTOR::update_predictor(const branch_record_c* br, const op_state_c* os, bool taken, uint actual_target_address)
{
	// UNCOMMENT FOR PREDICTION DEBUGGING
	// if (is_debugger_initialized == false){ 																					//<--- Debug
	// 	if (initialize_debugger("res.txt"))																			//<--- Debug	
	// 		is_debugger_initialized = true;																					//<--- Debug		
	// 	else																												//<--- Debug
	// 		exit(100);																										//<--- Debug	
	// }																														//<--- Debug																																				
	// write_prediction("res.txt", br, taken, actual_target_address); 	// write prediction to file								//<--- Debug
	update_statistics("stat.txt", br);

    if (br->is_conditional & br->is_call == false & br->is_call == false) 
    {
    	if(taken)												// if the branch is taken
    		local_history[actual_target_address]++;				// push 1 in the shift reg	
    	else 													// else 
    		local_history[actual_target_address]--; 			// push 0 in the shift reg
    }			
}